/**
 * 31.下一个排序
 */
public class Exerciser4 {
    public void nextPermutation(int[] nums) {
        // 1. 从右往左进行遍历查找第一个减小的值，那么这个减小的值就是设为 x (那么x后面的数都是递减的)(比如：1 3 5 4 2)(x为3)
        int n = nums.length;
        int i = n - 2;
        while(i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // i位置就是x 的值
        // 2. 如果x 的下标是小于0的，那么就直接进行第三步；反之需要，再次从右往左寻找第一个大于x 的值的下标(也就比如上述的4)
        //    之后进行将其 和 x进行交换 (就变为 1 4 5 3 2)
        if(i >= 0) {
            int j = n - 1;
            while(j >= i && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums,i,j);
        }
        // 3. 翻转 x 之后的数据 (就为 1 4 2 3 5)
        reverse(nums,i + 1,n - 1);
    }

    public void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public void reverse(int[] nums,int left,int right) {
        while(left <= right) {
            swap(nums,left++,right--);
        }
    }
}
